package com.suxin.algorithm.linked;

import lombok.Data;

/**
 * @author Tang
 * @classname SimpleLinked
 * @description [ 单链表 ]
 * @date 2022/3/29 22:31
 */
public class SimpleLinked<T> {

    // 头结点
    private Node head;
    // 元素个数
    private int size;

    public SimpleLinked() {
        this.head = null;
        this.size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean idEmpty() {
        return this.size == 0;
    }

    /**
     * 添加头
     * @param t
     */
    public void addHead(T t) {
        this.head = new Node<T>(t, this.head);
        this.size++;
    }

    /**
     * 添加尾
     * @param t
     */
    public void addTail(T t) {
        addPosition(t,this.size);
    }

    /**
     * 添加到指定元素的前面
     * 采用虚拟节点的方式
     * @param t 要插入在的指定元素前面
     * @param des // 要插入的内容
     */
    public void addEle(T t, T des) {
        // 虚拟节点，方便找到pre节点
        Node dummy = new Node(null, this.head);
        while (dummy.next != null) {
            if (!dummy.next.data.equals(t)) {
                dummy = dummy.next;
                continue;
            }
            break;
        }
        dummy.next = new Node(des, dummy.next);
        this.size++;
    }

    /**
     * 虚拟节点的方式删除,删除指定元素
     * 虚拟节点的作用，不需要使用pre节点了
     * @param t
     */
    public void removeEle(T t) {
        Node dummy = new Node(null, this.head);
        Node cur = dummy;
        while (dummy.next != null) {
            // 直接越过一个
            if (dummy.next.data.equals(t)) {
                dummy.next = dummy.next.next;
                this.size--;
                continue;
            }
            dummy = dummy.next;
        }
        this.head = cur.next;
    }

    /**
     * 添加到指定位置
     * @param t
     * @param index
     */
    public void addPosition(T t, int index) {
        if (index < 0 || index > this.size) {
            throw new IllegalArgumentException("index is error");
        }
        if (index == 0) {
            this.addHead(t);
        }
        Node temp = this.head;
        // 前插法
        for (int i = 0; i < index - 1; i++) {
            temp = temp.next;
        }
        temp.next = new Node(t, temp.next);
        this.size++;
    }

    /**
     * 移除指定的元素
     * @param t
     */
    public void remove(T t) {
        if (head == null) {
            System.out.println("无元素可删除!");
            return;
        }
        // 删除的是头元素
        while (head != null && head.data.equals(t)) {
            head = head.next;
            this.size--;
        }
        // 删除其他元素
        Node cur = this.head;
        while (cur != null && cur.next != null) {
            // 相等的话，，直接链向下一个
            if (cur.next.data.equals(t)) {
                this.size--;
                cur.next = cur.next.next;
            }else {
                cur = cur.next;
            }
        }
    }

    /**
     * 移除第一个
     * @return
     */
    public T removeFirst() {
        if (this.head == null) {
            System.out.println("无元素可删除!");
        }
        Node delNode = this.head;
        this.head = delNode.next;
        this.size--;
        delNode.next = null;
        return (T) delNode.data;
    }

    /**
     * 移除最后一个
     * @return
     */
    public T removeLast() {
        if (this.head == null) {
            System.out.println("无元素可删除!");
        }
        if (this.getSize() == 1) {
            return this.removeFirst();
        }
        Node cur = this.head;
        Node pre = this.head;
        while (cur.next != null) {
            pre = cur;
            cur = cur.next;
        }
        pre.next = cur.next;
        return (T) cur.data;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node cur = this.head;
        while (cur != null) {
            sb.append(cur.data).append("-->");
            cur = cur.next;
        }
        sb.append("NULL");
        return sb.toString();
    }

    public static void main(String[] args) {
        SimpleLinked<Integer> simpleLinked = new SimpleLinked<>();
        for (int i = 0; i < 10; i++) {
            simpleLinked.addHead(i);
        }
        simpleLinked.addHead(33);
        simpleLinked.addTail(33);
        simpleLinked.addPosition(33,5);
        System.out.println(simpleLinked);
        System.out.println("删除第一个元素:--->" + simpleLinked.removeFirst());
        System.out.println("删除最后一个元素:--->" + simpleLinked.removeLast());
        System.out.println(simpleLinked);
        simpleLinked.addEle(1,33);
        System.out.println(simpleLinked);
        simpleLinked.removeEle(33);
        System.out.println("移除元素为33的节点:" + simpleLinked);
    }

    @Data
    private static class Node<T> {

        private T data;

        private Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }

        public Node(T data) {
            this(data, null);
        }
    }

}

